#region Copyright Notice
// 
// 
//  
//  Copyright (c) 2009-2011 Anindya Chatterjee
//  
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the License.
//  You may obtain a copy of the License at
//  
//      http://www.apache.org/licenses/LICENSE-2.0
//  
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
// 
// 
#endregion
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using System.Xml;
using System.Xml.Schema;
using System.Xml.Serialization;
using AbstractClass.Extensions;

namespace AbstractClass.Collections.Graph
{
    /// <summary>
    /// Represents a data-structure consists mainly of a finite (and possibly mutable) set of 
    /// ordered pairs, called edges or arcs, of certain entities called nodes or vertices.
    /// </summary>
    /// <typeparam name="T">The type of the data in the collection.</typeparam>
    [Serializable]
    public class Graph<T> : IEnumerable<T>, IXmlSerializable, IAlgorithmAware<Graph<T>>
    {
        private readonly GraphEdgeCollection<T> _edgeList = new GraphEdgeCollection<T>();
        private readonly GraphNodeCollection<T> _nodeList = new GraphNodeCollection<T>();

        /// <summary>
        /// Gets the list of the nodes in the <see cref="Graph&lt;T&gt;"/> 
        /// as a read-only collection.
        /// </summary>
        /// <value>The list of nodes.</value>
        public ReadOnlyCollection<GraphNode<T>> NodeList
        {
            get { return new ReadOnlyCollection<GraphNode<T>>(_nodeList); }
        }

        /// <summary>
        /// Gets the list of the edges in the <see cref="Graph&lt;T&gt;"/> as 
        /// a read-only collection.
        /// </summary>
        /// <value>The list of edges.</value>
        public ReadOnlyCollection<GraphEdge<T>> Edges
        {
            get { return new ReadOnlyCollection<GraphEdge<T>>(_edgeList); }
        }

        /// <summary>
        /// Gets the number of nodes in the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <value>The number of nodes.</value>
        public int Count
        {
            get { return _nodeList.Count; }
        }

        #region IEnumerable<T> Members

        /// <summary>
        ///   Returns an enumerator that iterates through the collection.
        /// </summary>
        /// <returns>
        ///   A <see cref = "IEnumerator&lt;T&gt;" /> that can be used to iterate through the collection.
        /// </returns>
        public IEnumerator<T> GetEnumerator()
        {
            return NodeList.Select(gnode => gnode.Value).GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        #region IXmlSerializable Members

        XmlSchema IXmlSerializable.GetSchema()
        {
            return null;
        }

        void IXmlSerializable.ReadXml(XmlReader reader)
        {
            var nodeSerializer = new XmlSerializer(typeof (GraphNode<T>));
            var edgeSerializer = new XmlSerializer(typeof (GraphEdge<T>));
            bool wasEmpty = reader.IsEmptyElement;
            reader.Read();

            if (wasEmpty)
                return;

            reader.ReadStartElement("Nodes");
            while (reader.NodeType != XmlNodeType.EndElement)
            {
                reader.ReadStartElement("node");
                var node = (GraphNode<T>) nodeSerializer.Deserialize(reader);
                reader.ReadEndElement();
                Add(node);
                reader.MoveToContent();
            }
            reader.ReadEndElement();

            reader.ReadStartElement("Edges");
            while (reader.NodeType != XmlNodeType.EndElement)
            {
                reader.ReadStartElement("edge");
                var edge = (GraphEdge<T>) edgeSerializer.Deserialize(reader);
                GraphNode<T> sourceNode = _nodeList.FindByValue(edge.Source.Value);
                GraphNode<T> destinationNode = _nodeList.FindByValue(edge.Destination.Value);
                edge.Source = sourceNode;
                edge.Destination = destinationNode;
                reader.ReadEndElement();
                Add(edge);
                reader.MoveToContent();
            }
            reader.ReadEndElement();
        }

        void IXmlSerializable.WriteXml(XmlWriter writer)
        {
            var nodeSerializer = new XmlSerializer(typeof (GraphNode<T>));
            var edgeSerializer = new XmlSerializer(typeof (GraphEdge<T>));

            writer.WriteStartElement("Nodes");
            foreach (var graphNode in NodeList)
            {
                writer.WriteStartElement("node");
                nodeSerializer.Serialize(writer, graphNode);
                writer.WriteEndElement();
            }
            writer.WriteEndElement();

            writer.WriteStartElement("Edges");
            foreach (var graphEdge in Edges)
            {
                writer.WriteStartElement("edge");
                edgeSerializer.Serialize(writer, graphEdge);
                writer.WriteEndElement();
            }
            writer.WriteEndElement();
        }

        #endregion

        #region Graph Operations

        /// <summary>
        /// Adds the specified <paramref name="node"/> in the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="node">The node to add.</param>
        public void Add(GraphNode<T> node)
        {
            node.ThrowIfNull("node");
            _nodeList.Add(node);
            node.Owner = this;
        }

        /// <summary>
        /// Adds the specified value as a node in the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="value">The value to add.</param>
        public void Add(T value)
        {
            var node = new GraphNode<T>(value);
            Add(node);
        }

        /// <summary>
        /// Adds the specified <paramref name="edge"/> in the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="edge">The edge to add.</param>
        public void Add(GraphEdge<T> edge)
        {
            if (!_nodeList.Contains(edge.Source) || !_nodeList.Contains(edge.Destination))
                return;
            edge.Owner = this;
            _edgeList.Add(edge);
        }

        /// <summary>
        /// Adds the specified directed edge in the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="fromValue">Source node value.</param>
        /// <param name="toValue">Destination node value.</param>
        /// <exception cref="ArgumentException">Source / Destination node not found in the <see cref="Graph&lt;T&gt;"/>.</exception>
        public void AddDirectedEdge(T fromValue, T toValue)
        {
            AddDirectedEdge(fromValue, toValue, 0);
        }

        /// <summary>
        /// Adds the specified directed edge in the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="fromNode">Source node.</param>
        /// <param name="toNode">Destination node.</param>
        /// <exception cref="ArgumentException">Source / Destination node not found in the <see cref="Graph&lt;T&gt;"/>.</exception>
        public void AddDirectedEdge(GraphNode<T> fromNode, GraphNode<T> toNode)
        {
            AddDirectedEdge(fromNode, toNode, 0);
        }

        /// <summary>
        /// Adds the specified directed edge in the <see cref="Graph&lt;T&gt;"/> tagged with <paramref name="cost"/>.
        /// </summary>
        /// <param name="fromNode">Source node.</param>
        /// <param name="toNode">Destination node.</param>
        /// <param name="cost">The cost associated with the edge.</param>
        /// <exception cref="ArgumentException">Source / Destination node not found in the <see cref="Graph&lt;T&gt;"/>.</exception>
        public void AddDirectedEdge(GraphNode<T> fromNode, GraphNode<T> toNode, int cost)
        {
            fromNode.ThrowIfNull("fromNode");
            toNode.ThrowIfNull("toNode");

            if (!_nodeList.Contains(fromNode))
                throw new ArgumentException(LanguageResource.SourceNodeNotFoundInTheGraph, "fromNode");

            if (!_nodeList.Contains(toNode))
                throw new ArgumentException(LanguageResource.DestinationNodeNotFoundInTheGraph, "toNode");

            if (!_nodeList.Contains(fromNode) || !_nodeList.Contains(toNode)) return;
            _edgeList.Add(new GraphEdge<T>(fromNode, toNode, cost) {IsDirected = true, Owner = this});
            return;
        }

        /// <summary>
        /// Adds the specified directed edge in the <see cref="Graph&lt;T&gt;"/> tagged with <paramref name="cost"/>.
        /// </summary>
        /// <param name="fromValue">Value associated with the source node.</param>
        /// <param name="toValue">Value associated with the destination node.</param>
        /// <param name="cost">The cost associated with the edge.</param>
        /// <exception cref="ArgumentException">Source / Destination node not found in the <see cref="Graph&lt;T&gt;"/>.</exception>
        public void AddDirectedEdge(T fromValue, T toValue, int cost)
        {
            GraphNode<T> fromNode = _nodeList.FindByValue(fromValue);
            GraphNode<T> toNode = _nodeList.FindByValue(toValue);
            if (fromNode == null)
                throw new ArgumentException(LanguageResource.SourceNodeNotFoundInTheGraph, "fromValue");
            if (toNode == null)
                throw new ArgumentException(LanguageResource.DestinationNodeNotFoundInTheGraph, "toValue");

            AddDirectedEdge(fromNode, toNode, cost);
        }

        /// <summary>
        /// Adds the specified undirected edge in the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="fromNode">Value associated with source node.</param>
        /// <param name="toNode">Value associated with destination node.</param>
        /// <exception cref="ArgumentException">Source / Destination node not found in the <see cref="Graph&lt;T&gt;"/>.</exception>
        public void AddUndirectedEdge(T fromNode, T toNode)
        {
            AddUndirectedEdge(fromNode, toNode, 0);
        }

        /// <summary>
        /// Adds the specified undirected edge in the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="fromNode">Source node.</param>
        /// <param name="toNode">Destination node.</param>
        /// <exception cref="ArgumentException">Source / Destination node not found in the <see cref="Graph&lt;T&gt;"/>.</exception>
        public void AddUndirectedEdge(GraphNode<T> fromNode, GraphNode<T> toNode)
        {
            AddUndirectedEdge(fromNode, toNode, 0);
        }

        /// <summary>
        /// Adds the specified undirected edge in the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="fromNode">Source node.</param>
        /// <param name="toNode">Destination node.</param>
        /// <param name="cost">The cost associated with the edge.</param>
        /// <exception cref="ArgumentException">Source / Destination node not found in the <see cref="Graph&lt;T&gt;"/>.</exception>
        public void AddUndirectedEdge(GraphNode<T> fromNode, GraphNode<T> toNode, int cost)
        {
            if (_nodeList.Contains(fromNode) && _nodeList.Contains(toNode))
            {
                _edgeList.Add(new GraphEdge<T>(fromNode, toNode, cost) {IsDirected = false, Owner = this});
                return;
            }

            if (!_nodeList.Contains(fromNode))
                throw new ArgumentException(LanguageResource.SourceNodeNotFoundInTheGraph, "fromNode");

            if (_nodeList.Contains(toNode))
                throw new ArgumentException(LanguageResource.DestinationNodeNotFoundInTheGraph, "toNode");
        }

        /// <summary>
        /// Adds the specified undirected edge in the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="fromValue">Value associated with source node.</param>
        /// <param name="toValue">Value associated with destination node.</param>
        /// <param name="cost">The cost associated with the edge.</param>
        /// <exception cref="ArgumentException">Source / Destination node not found in the <see cref="Graph&lt;T&gt;"/>.</exception>
        public void AddUndirectedEdge(T fromValue, T toValue, int cost)
        {
            GraphNode<T> fromNode = _nodeList.FindByValue(fromValue);
            GraphNode<T> toNode = _nodeList.FindByValue(toValue);
            if (fromNode == null)
                throw new ArgumentException(LanguageResource.SourceNodeNotFoundInTheGraph, "fromValue");
            if (toNode == null)
                throw new ArgumentException(LanguageResource.DestinationNodeNotFoundInTheGraph, "toValue");

            AddUndirectedEdge(fromNode, toNode, cost);
        }

        /// <summary>
        /// Determines whether <paramref name="node"/> is in the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="node">The node to find.</param>
        /// <returns>
        /// <see cref="GraphNode&lt;T&gt;"/> associated with <paramref name="node"/> if found; otherwise <c>null</c>.
        /// </returns>
        public GraphNode<T> FindNode(T node)
        {
            return _nodeList.FirstOrDefault(item => item.Value.Equals(node));
        }

        /// <summary>
        /// Gets all edges, specified by source value and destination value, found in the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="fromNode">Value associated with source node.</param>
        /// <param name="toNode">Value associated with destination node.</param>
        /// <returns>A collection of <see cref="GraphEdge&lt;T&gt;"/> found in the <see cref="Graph&lt;T&gt;"/>.</returns>
        public IEnumerable<GraphEdge<T>> GetEdges(T fromNode, T toNode)
        {
            return _edgeList.Where(item => (item.Source.Value.Equals(fromNode) && item.Destination.Value.Equals(toNode))
                                           ||
                                           (item.Source.Value.Equals(toNode) && item.Destination.Value.Equals(fromNode)));
        }

        /// <summary>
        /// Gets all edges, specified by source value, destination value and cost, found in the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="fromNode">Value associated with source node.</param>
        /// <param name="toNode">Value associated with destination node.</param>
        /// <param name="cost">The cost associated with edges.</param>
        /// <returns>A collection of <see cref="GraphEdge&lt;T&gt;"/> found in the <see cref="Graph&lt;T&gt;"/>.</returns>
        public IEnumerable<GraphEdge<T>> GetEdges(T fromNode, T toNode, int cost)
        {
            return
                _edgeList.Where(
                    item =>
                    item.Cost == cost && ((item.Source.Value.Equals(fromNode) && item.Destination.Value.Equals(toNode))
                                          ||
                                          (item.Source.Value.Equals(toNode) && item.Destination.Value.Equals(fromNode))));
        }

        /// <summary>
        /// Removes all edges and nodes from this instance.
        /// </summary>
        public void Clear()
        {
            _nodeList.Clear();
            _edgeList.Clear();
        }

        /// <summary>
        /// Removes all edges from this instance.
        /// </summary>
        public void ClearEdges()
        {
            _edgeList.Clear();
        }

        /// <summary>
        /// Determines whether the specified value is in the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="value">The value to find in the <see cref="Graph&lt;T&gt;"/>.</param>
        /// <returns>
        /// 	<c>true</c> if found; otherwise, <c>false</c>.
        /// </returns>
        public bool Contains(T value)
        {
            return _nodeList.FindByValue(value) != null;
        }

        /// <summary>
        /// Determines whether the specified node is in the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="node">The node to find in the <see cref="Graph&lt;T&gt;"/>.</param>
        /// <returns>
        /// 	<c>true</c> if found; otherwise, <c>false</c>.
        /// </returns>
        public bool Contains(GraphNode<T> node)
        {
            return _nodeList.Contains(node);
        }

        /// <summary>
        /// Determines whether the specified edge is in the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="edge">The edge to find in the <see cref="Graph&lt;T&gt;"/>.</param>
        /// <returns>
        /// 	<c>true</c> if the specified edge is in the <see cref="Graph&lt;T&gt;"/>; otherwise, <c>false</c>.
        /// </returns>
        public bool ContainsEdge(GraphEdge<T> edge)
        {
            return _edgeList.Contains(edge);
        }

        /// <summary>
        /// Determines whether the specified edge is in the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="fromNode">Source node.</param>
        /// <param name="toNode">Destination node.</param>
        /// <returns>
        /// 	<c>true</c> if found; otherwise, <c>false</c>.
        /// </returns>
        public bool ContainsEdge(GraphNode<T> fromNode, GraphNode<T> toNode)
        {
            return _edgeList.Contains(fromNode, toNode);
        }

        /// <summary>
        /// Determines whether the specified edge is in the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="fromNode">Value associated with source node.</param>
        /// <param name="toNode">Value associate with destination node.</param>
        /// <returns>
        /// 	<c>true</c> if found; otherwise, <c>false</c>.
        /// </returns>
        public bool ContainsEdge(T fromNode, T toNode)
        {
            return _edgeList.Contains(fromNode, toNode);
        }

        /// <summary>
        /// Determines whether the specified edge is in the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="fromNode">Source node.</param>
        /// <param name="toNode">Destination node.</param>
        /// <param name="cost">The cost associated with the edge.</param>
        /// <returns>
        /// 	<c>true</c> if found; otherwise, <c>false</c>.
        /// </returns>
        public bool ContainsEdge(GraphNode<T> fromNode, GraphNode<T> toNode, int cost)
        {
            return _edgeList.Contains(fromNode, toNode, cost);
        }

        /// <summary>
        /// Determines whether the specified edge is in the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="fromNode">Value associated with source node.</param>
        /// <param name="toNode">Value associated with destination node.</param>
        /// <param name="cost">The cost associated with the edge.</param>
        /// <returns>
        /// 	<c>true</c> if found; otherwise, <c>false</c>.
        /// </returns>
        public bool ContainsEdge(T fromNode, T toNode, int cost)
        {
            return _edgeList.Contains(fromNode, toNode, cost);
        }

        /// <summary>
        /// Removes a node specified by <paramref name="value"/> from the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="value">The value to remove from <see cref="Graph&lt;T&gt;"/>.</param>
        /// <returns>
        /// <c>true</c> if removed successfully; otherwise, <c>false</c>.
        /// </returns>
        public bool Remove(T value)
        {
            GraphNode<T> node = _nodeList.FindByValue(value);
            return Remove(node);
        }

        /// <summary>
        /// Removes the specified node from the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="node">The node to remove from the <see cref="Graph&lt;T&gt;"/>.</param>
        /// <returns>
        /// <c>true</c> if removed successfully; otherwise, <c>false</c>.
        /// </returns>
        public bool Remove(GraphNode<T> node)
        {
            return node != null && _nodeList.Remove(node);
        }

        /// <summary>
        /// Removes the specified edge from the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="edge">The edge to remove from the <see cref="Graph&lt;T&gt;"/>.</param>
        /// <returns>
        /// <c>true</c> if removed successfully; otherwise, <c>false</c>.
        /// </returns>
        public bool RemoveEdge(GraphEdge<T> edge)
        {
            return edge != null && _edgeList.Remove(edge);
        }

        /// <summary>
        /// Removes a range of edges from the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="edges">The edges to remove from the <see cref="Graph&lt;T&gt;"/>.</param>
        /// <returns>
        /// <c>true</c> if all edges removed successfully; otherwise, <c>false</c>.
        /// </returns>
        public bool RemoveEdges(IEnumerable<GraphEdge<T>> edges)
        {
            return edges != null && _edgeList.RemoveAll(edges);
        }

        /// <summary>
        /// Removes the specified edge from the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="fromNode">Source node.</param>
        /// <param name="toNode">Destination node.</param>
        /// <returns>
        /// <c>true</c> if removed successfully; otherwise, <c>false</c>.
        /// </returns>
        public bool RemoveEdge(GraphNode<T> fromNode, GraphNode<T> toNode)
        {
            return _edgeList.Remove(fromNode, toNode);
        }

        /// <summary>
        /// Removes the specified edge from the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="fromNode">Source node.</param>
        /// <param name="toNode">Destination node.</param>
        /// <param name="cost">The cost associated with the edge.</param>
        /// <returns>
        /// <c>true</c> if removed successfully; otherwise, <c>false</c>.
        /// </returns>
        public bool RemoveEdge(GraphNode<T> fromNode, GraphNode<T> toNode, int cost)
        {
            return _edgeList.Remove(fromNode, toNode, cost);
        }

        /// <summary>
        /// Removes the specified edge from the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="fromNode">Value associated with source node.</param>
        /// <param name="toNode">Values associated with destination node.</param>
        /// <returns>
        /// <c>true</c> if removed successfully; otherwise, <c>false</c>.
        /// </returns>
        public bool RemoveEdge(T fromNode, T toNode)
        {
            return _edgeList.Remove(fromNode, toNode);
        }

        /// <summary>
        /// Removes the specified edge from the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <param name="fromNode">Value associated with source node.</param>
        /// <param name="toNode">Values associated with destination node.</param>
        /// <param name="cost">The cost associated with the edge.</param>
        /// <returns>
        /// <c>true</c> if removed successfully; otherwise, <c>false</c>.
        /// </returns>
        public bool RemoveEdge(T fromNode, T toNode, int cost)
        {
            return _edgeList.Remove(fromNode, toNode, cost);
        }

        #endregion

        #region Graph Properties

        /// <summary>
        /// Determines whether this instance is a directed graph.
        /// </summary>
        /// <value>
        /// 	<c>true</c> if this instance is directed graph; otherwise, <c>false</c>.
        /// </value>
        public bool IsDirectedGraph
        {
            get { return Edges.All(graphEdge => graphEdge.IsDirected); }
        }

        /// <summary>
        /// Gets the order of this instance.
        /// </summary>
        /// <value>The order of the <see cref="Graph&lt;T&gt;"/>.</value>
        public int Order
        {
            get { return Count; }
        }

        /// <summary>
        /// Gets the number of edges in this instance.
        /// </summary>
        /// <value>The number of edges in the <see cref="Graph&lt;T&gt;"/>.</value>
        public int Size
        {
            get { return Edges.Count; }
        }

        #endregion

        #region Implementation of IAlgorithmAware<out Graph<T>>

        /// <summary>
        /// Executes the <paramref name="algorithm"/> on the <see cref="Graph&lt;T&gt;"/>.
        /// </summary>
        /// <typeparam name="TResult">The type of the result.</typeparam>
        /// <param name="algorithm">The algorithm to run on the <see cref="Graph&lt;T&gt;"/>.</param>
        /// <returns>The result of execution of the <paramref name="algorithm"/> on the <see cref="Graph&lt;T&gt;"/>.</returns>
        public TResult ExecuteAlgorithm<TResult>(IAlgorithm<Graph<T>, TResult> algorithm)
        {
            algorithm.ThrowIfNull("algorithm");
            return algorithm.Run(this);
        }

        #endregion
    }
}